package com.berchen.算法;

import java.time.Duration;
import java.time.Instant;

/**
 * 冒泡排序
 * 两两进行比较
 * 第一个元素和第二个比较 将大/小的元素换到后面
 * 第二个元素与第三个比较 将大/小的元素换到后面
 * 。。。
 * 当走完一轮之后 最后一个元素就是最大/小的元素。
 *
 * 以此类推。
 *
 * 对程序优化：当有一趟没有进行一次交换数据 就说明数据已经是有序的了。
 */
public class BubbleSort {

    public static void main(String[] args) {

        int [] arr={-1,1,4,2,10,-5};
        int [] testArr=new int[80000];
        for(int i =0;i<testArr.length;i++){
            testArr[i]= (int) (Math.random()*80000);
        }
       // for(int i =0;i<testArr.length;i++){
       //     System.out.printf("%d\t",testArr[i]);
       // }
        Instant start = Instant.now();
        bubbleSort2(testArr);
        Instant end = Instant.now();
        System.out.println(Duration.between(start, end).toMillis());    // 12047  毫秒
       // for(int i =0;i<testArr.length;i++){
       //     System.out.printf("%d\t",testArr[i]);
       // }

    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int [] arr){
        for(int i =0;i<arr.length-1;i++){
//            System.out.println(i);
            boolean flag=false; // 通过这个优化程序，当有一趟没有进行数据交换就说明已经排序好了数据
            for(int j =0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    flag=true;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag) { // 在这趟里面 一次都没有交换数据
                break;
            }
        }
    }

    /**
     * 冒泡优化
     */
    public static void bubbleSort2(int[] arr) {
        // 冒泡每一次需要比较的次数
        int n = arr.length - 1;
        while (true) {
            // 本轮冒泡中，最后一次交换时，就代表该索引后面的元素都是有序的了。
            int last = 0; // 记录最后一次交换时，前一个元素的索引  比如：7 和 4 交换，记录7 的索引。
            for (int i = 0; i < n; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;

                    last = i; // 记录每次交换时候前一个元素的索引，本轮冒泡结束后，该值就是最后一次交换时，前一个元素的索引了
                }
            }
            n = last;
            if (n == 0) {
                break;
            }
        }
    }
}
